A decoder is typically implemented in a receiver that receives data bits over a communication link from a transmitter. When the communication link is noisy, the reception of the data bits over the communication link usually results in errors. To identify and correct such errors, the data bits are typically encoded, before transmitting, using an error correcting code. One example of such error correcting code is a Bose-Chaudhuri-Hocquenghem (BCH) code that is defined over a finite field such as a Galois Field GF(2m), where ‘m’ is a positive integer. Upon receiving the encoded data bits, a BCH decoder decodes the encoded data bits to identify erroneous data bits. Further, the erroneous data bits are inverted to rectify the errors. The decoding of the encoded data bits includes determining syndrome vectors based on the reception of the encoded data bits, determining an error locator polynomial (ELP) based on the syndrome vectors, and solving the ELP to identify the erroneous data bits in the encoded data bits. A known method to solve the ELP is a brute force method that may be performed by a circuit that implements a Chien search algorithm.
FIG. 1 illustrates a block diagram of a conventional parallel Chien search circuit (PCSC) 100 of a conventional BCH decoder (not shown) that solves the ELP for identifying the erroneous data bits. The PCSC 100 includes a feedback circuit 102 and a substitution circuit 104. The feedback circuit 102 includes first through tth multiplexers 106a-106t, first through tth multipliers 108a-108t, first through tth registers 110a-110t, and a first adder 112. The first multiplexer 106a receives a first input λ1 from a key equation solver (KES) circuit (not shown) which is external to the PCSC 100. The first input λ1 is a first co-efficient of the ELP. The ELP is shown in equation (1) as:λ(x)=1+λ1·x1+λ2·x2+ . . . +λt·xt  (1)where ‘t’ is number of erroneous data bits that are correctable by the PCSC 100, and ‘x’ is a non-zero field element of the Galois Field GF(2m). Field elements of the Galois Field GF(2m), having a primitive element ‘α’ are {0 α1α2 . . . α(p−1) αp α(p+1) . . . α((2{circumflex over ( )}m)−1)}, where ‘p’ is number of data bits processed per cycle for solving the ELP. The conventional BCH decoder receives ‘n’ number of data bits such that ‘n≤(2m−1)’. Therefore, x={α1 α2 . . . α(p−1) αp α(p+1) . . . αn}. Further, the field elements are constant for a BCH decoder and hence, are stored in a memory (not shown) associated with the PCSC 100.
The first multiplexer 106a is connected to the first register 110a for receiving a second input f1. The first multiplexer 106a selects and outputs one of the first or second inputs λ1 or f1 based on a select line (not shown). Similarly, the second through tth multiplexers 106b-106t receive corresponding first inputs λ2-λt from the KES circuit, and corresponding second inputs f2-ft from the second through tth registers 110b-110t, respectively. The second through tth multiplexers 106b-106t select and output one of the first inputs λ2-λt or second inputs f2-ft, respectively, based on the corresponding select lines.
The first multiplier 108a is connected to the first multiplexer 106a for receiving a third input i1, i.e., an output (λ1 or f1) of the first multiplexer 106a. The first multiplier 108a is further connected to the memory for receiving a fourth input αp. The fourth input αp is a field element of the Galois Field GF(2m). The first multiplier 108a multiplies the third and fourth inputs i1 and αp, and generates a first multiplication output x1. The first register 110a is connected to the first multiplier 108a for receiving the first multiplication output x1. The first register 110a may be a D-latch that outputs the first multiplication output x1 when the first register 110a is triggered by a clock signal (not shown). Similarly, the second through tth multipliers 108b-108t are connected to the second through tth multiplexers 106b-106t for receiving corresponding third inputs i2-it, and the memory for receiving corresponding fourth inputs α(2*p)-α(t*p). The second through tth multipliers 108b-108t multiply the corresponding third and fourth inputs i2-it and α(2*p)-α(t*p), and generate second through tth multiplication outputs x2-xt, respectively. Further, the second through tth registers 110b-110t are connected to the second through tth multipliers 108b-108t for receiving the second through tth multiplication outputs x2-xt, respectively. Thus, the first through tth multipliers 108a-108t output a first set of multiplication outputs (i.e., first through tth multiplication outputs x1-xt).
The first adder 112 is connected to the first through tth multipliers 108a-108t for receiving the first through tth multiplication outputs x1-xt, respectively. The first adder 112 generates a first sum Yp based on a summation of the first through tth multiplication outputs x1-xt. The first sum Yp is shown in equation (2) as:Yp=i1·αp+i2·α2*p+ . . . +it·αt*p  (2)when i1-it=λ1-λt, the first sum Yp is shown in equation (3) as:Yp=λ1·αp+λ2·α2*p+ . . . +λt·αt*p  (3)From the equations (1) and (3), Yp=λ(x)−1, for x=αp. To solve the ELP for x=αp, ‘1’ is added to the first sum Yp by an adder (not shown) which is external to the PCSC 100. If ‘1+Yp=0’, a presence of an error in a pth data bit is detected. To correct the error, a current value of the pth data bit is inverted.
The substitution circuit 104 includes multipliers 114_11-114_zt that are arranged in an arrangement as illustrated in FIG. 1. The arrangement includes first through (p−1)th rows and first through tth columns. The first row includes ‘t’ number of multipliers [114_11 114_12 . . . 114_1t] arranged in the first through tth columns, respectively. Similarly, the second through (p−1)th rows include multipliers [114_21 114_22 . . . 114_2t] through [114_z1 114_z2 . . . 114_zt] arranged in the first through tth columns, respectively. Thus, the first column includes multipliers [114_11 114_21 . . . 114_z1]. Similarly, the second through tth columns include multipliers [114_12 114_22 . . . 114_z2] through [114_1t 114_2t . . . 114_zt], respectively. The substitution circuit 104 further includes second through pth adders 116a-116z. 
The multipliers [114_11 114_21 . . . 114_z1] in the first column are connected to the first multiplexer 106a for receiving corresponding third inputs i1. Similarly, the multipliers [114_11 114_21 . . . 114_z1] are connected to the memory for receiving corresponding fourth inputs [α α2 . . . α(p−1)]. For example, the multiplier 114_11 receives i1 and ‘α’ as the corresponding third and fourth inputs. Similarly, the multipliers [114_12 114_22 . . . 114_z2] through [114_1t 114_2t . . . 114_zt] are connected to the second through tth multiplexers 106b-106t for receiving corresponding third inputs i2-it, and the memory for receiving corresponding fourth inputs [α2 α2*2 . . . α2*(p−1)]-[αt αt*2 . . . αt*(p−1)]. The multipliers [114_11 114_12 . . . 114_1t] multiply the corresponding third and fourth inputs to generate a second set of multiplication outputs [x11 x12 . . . x1t], respectively. Similarly, the multipliers [114_21 114_22 . . . 114_2t] through [114_z1 114_z2 . . . 114_zt] multiply the corresponding third and fourth inputs, and generate third through pth sets of multiplication outputs [x21 x22 . . . x2t]-[xz1 xz2 . . . xzt], respectively.
The second adder 116a is connected to the multipliers [114_11 114_12 . . . 114_1t] of the first row for receiving the second set of multiplication outputs [x11 x12 . . . x1t]. The second adder 116a generates a second sum Y1 based on a summation of the second set of multiplication outputs [x11 x12 . . . x1t]. If ‘1+Y1=0’, a presence of an error in a first data bit is detected. To correct the error, a current value of the first data bit is inverted. Similarly, the third through pth adders 116b-116z are connected to the multipliers [114_21 114_22 . . . 114_2t] through [114_z1 114_z2 . . . 114_zt] for receiving the third through pth sets of multiplication outputs [x21 x22 . . . x2t]-[xz1 xz2 . . . xzt], respectively. The third through pth adders 116b-116z generate third through pth sums Y2-Y(p−1) based on summations of the third through pth sets of multiplication outputs [x21 x22 . . . x2t]-[xz1 xz2 . . . xzt], respectively.
The PCSC 100 solves the ELP for the field elements of the Galois Field GF(2m) in first through (n/p)th cycles. In the first cycle, the first through tth multiplexers 106a-106t select and output the corresponding first inputs λ1-λt, i.e., i1-it=λ1-λt. Thus, the first multiplier 108a and the multipliers [114_11 114_21 . . . 114_z1] receive λ1 as the corresponding third inputs. Similarly, the second through tth multipliers 108b-108t and the multipliers [114_12 114_22 . . . 114_z2] through [114_1t 114_2t . . . 114_zt] receive λ2-λt, respectively, as the corresponding third inputs. The first through tth multipliers 108a-108t and the multipliers [114_11 114_12 . . . 114_1t] through [114_z1 114_z2 . . . 114_zt] further receive αp-α(t*p) and [α1 α2 . . . αt]-[α(p−1) α2*(p−1) . . . αt*(p−1)], respectively, as corresponding fourth inputs. Further, the first through tth multipliers 108a-108t and the multipliers 114_11-114_zt generate the first through pth sets of multiplication outputs based on the corresponding third and fourth inputs. The first adder 112 generates the first sum Yp based on the first set of multiplication outputs x1-xt. Similarly, the second through pth adders 116a-116z generate the second through pth sums Y1-Y(p−1) based on the second through pth sets of multiplication outputs [x11 x12 . . . x1t]-[xz1 xz2 . . . xzt], respectively. The first sum Yp and the second through pth sums Y1-Y(p−1) are individually added with ‘1’ to determine which of the first through pth data bits are erroneous. The erroneous data bits are corrected by inverting current values of the erroneous data bits. Further, the first through tth registers 110a-110t store the first through tth multiplication outputs x1-xt, respectively.
In the second cycle, the first through tth multiplexers 106a-106t select and output the second inputs f1-ft, i.e., i1-it=λ1·αp-λt·αt*p), respectively. The second inputs f1-ft are the first through tth multiplication outputs x1-xt (i.e., λ1·αp-λt·αt*p) of the first cycle, respectively. The first through tth multipliers 108a-108t and the multipliers [114_11 114_21 . . . 114_z1] through [114_1t 114_2t . . . 114_zt] receive λ1·αp-λt·αt*p as the corresponding third inputs, respectively. The first through tth multipliers 108a-108t and the multipliers [114_11 114_12 . . . 114_1t] through [114_z1 114_z2 . . . 114_zt] further receive αp-α(t*p) and [α1 α2 . . . αt]-[α(p−1) α2*(p−1) . . . αt*(p−1)], respectively, as the corresponding fourth inputs. The first through tth multipliers 108a-108t and the multipliers 114_11-114_zt generate the first through pth sets of multiplication outputs based on the corresponding third and fourth inputs. The first adder 112 generates the first sum Yp based on the first set of multiplication outputs x1-xt. Similarly, the second through pth adders 116a-116z generate the second through pth sums Y1-Y(p−1) based on the second through pth sets of multiplication outputs [x11 x12 . . . x1t]-[xz1 xz2 . . . xzt], respectively. The first sum Yp and the second through pth sums Y1-Y(p−1) are individually added with ‘1’ to determine which of the (p+1)th through (2*p)th data bits are erroneous. Thus, the PCSC 100 determines which of the first through nth data bits are erroneous data bits in ‘n/p’ cycles.
The above-described PCSC 100 is widely used in Application Specific Integrated Circuits (ASICs) associated with data error correction, as such ASICs offer a high degree of freedom to implement larger and complicated digital logic circuits. However, for implementing the PCSC 100 in an FPGA (not shown), data bits associated with the equation (1) are mapped into the FPGA which results in utilization of a large number of look-up tables (LUTs) in the FPGA. The utilization of the large number of LUTs results in complex interconnect routing among the LUTs in the FPGA, and an increase in power consumed by the conventional BCH decoder that includes the PCSC 100. Further, the conventional BCH decoder occupies a significant area on the FPGA due to the utilization of the large number of LUTs.
In light of the foregoing, it would be advantageous to have a method that simplifies logic associated with a PCSC and implements a BCH decoder which includes the PCSC that consumes low power and area as compared to conventional PCSCs.